# 翻转二叉树

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right



class Solution:
    def invertTree(self, root):
        if not root:
            return
        tmp = root.left
        root.left = root.right
        root.right = tmp
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root


# 通用数组转二叉树

def array_to_binary_tree(arr):
    if not arr:
        return None
    
    root = TreeNode(arr[0])
    queue = [root]
    i = 1

    while queue and i < len(arr):
        node = queue.pop(0)
        # 左子节点
        if i < len(arr):
            node.left = TreeNode(arr[i])
            queue.append(node.left)
            i += 1
        # 右子节点
        if i < len(arr):
            node.right = TreeNode(arr[i])
            queue.append(node.right)
            i += 1

        
    return root

# 层序遍历
def level_order_basic(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result



if __name__ == "__main__":


    arr = [4,2,7,1,3,6,9]

    root = array_to_binary_tree(arr=arr)
    
    a1 = level_order_basic(root)
    print(a1)
    sol = Solution()
    r = sol.invertTree(root)

    a2 = level_order_basic(r)
    print(a2)






